package com.algorithm.mergeTwolinked;

public class MergeTwolinked {
    public static void main(String[] args) {
        int[] arr1 = {1,3,5,7};
        int[] arr2 = {2,4,6,8,9};
        Node linkedList1 = create(arr1);
        Node linkedList2 = create(arr2);
        Node node = merge(linkedList1, linkedList2);
        print(node.getNext());
    }
    public static Node create(int[] arr){
        Node head = new Node(arr[0],null);
        Node p = head;
        for (int i = 1; i < arr.length; i++) {
            Node node = new Node(arr[i],null);
            p.setNext(node);
            p = node;
        }
        return head;
    }

    public static Node merge(Node head1, Node head2){
        Node head = new Node(0,null);
        Node p = head;
        while(head1 != null && head2 != null){
            if(head1.getData()<=head2.getData()){
                p.setNext(head1);
                head1 = head1.getNext();
            } else {
                p.setNext(head2);
                head2 = head2.getNext();
            }
            p = p.getNext();
        }
        if(head1 != null){
            p.setNext(head1);
        }
        if (head2 != null){
            p.setNext(head2);
        }
        return head;
    }

    public static void print(Node head){
        Node p = head;
        while(p!= null){
            System.out.println(p.getData());
            p = p.getNext();
        }
    }
}
